The present invention relates to computation in the finite field GF(2.sup.m) in general, and more particularly, to a multiplier for multiplying two elements in the finite field GF(2.sup.m).
The finite field GF(2.sup.m) is a number system containing 2.sup.m elements. Its attractiveness in practical applications stems from the fact that each element can be represented by m binary digits. The practical application of error-correcting codes makes considerable use of computation in GF(2.sup.m). Both the encoding and decoding devices for the important Reed-Solomon codes must perform computations in GF(2.sup.m). The decoding device for the binary Bose-Chaudhuri-Hocquenghem codes also must perform computation in GF(2.sup.m). The reader is referred to "Error-Correcting Codes" by W. W. Peterson and E. J. Weldon, Jr., 2nd Ed., the M.I.T. Press, 1972, for details of these and other applications of GF(2.sup.m) computation for error-correction. Recent advances in the art of secrecy coding also require the use of computation in GF(2.sup.m). The reader is referred to the letter "Implementing Public Key Scheme," by S. Berkovits, J. Kowalchuk and B. Schanning, IEEE Communications Magazine, Vol. 17, pp. 2-3, May 1979.
The finite field GF(2) is the number system in which the only elements are the binary numbers 0 and 1 and in which the rules of addition and multiplication are the following: EQU 0+0=1+1=0 EQU 0+1=1+0=1 EQU 0.times.0=1.times.0=0.times.1=0 EQU 1.times.1=1.
These rules are commonly called modulo-two arithmetic. The finite field GF(2.sup.m), where m is an integer greater than 1, is the number system in which there are 2.sup.m elements and in which the rules of addition and multiplication correspond to arithmetic modulo an irreducible polynomial of degree m with coefficients in GF(2). Although in an abstract sense there is for each m only one field GF(2.sup.m), the complexity of the logic circuitry required to perform operations in GF(2.sup.m) depends strongly on the particular way in which the field elements are represented.
The conventional approach to the design of logic circuitry to perform operations in GF(2.sup.m) is described in such papers as T. Bartee and D. Schneider, "Computation with Finite Fields", Information and Control, Vol. 6, pp. 79-98, 1963. In this conventional approach, one first chooses a polynomial P(X) of degree m which is irreducible over GF(2), that is, P(X) has binary coefficients but cannot be factored into a product of polynomials with binary coefficients each of whose degree is less than m. An element A in GF(2.sup.m) is then defined to be a root of P(X), that is, to satisfy P(A)=0. The fact that P(X) is irreducible guarantees that the m elements A.sup.0 =1, A, A.sup.2, . . . , A.sup.m-1 of GF(2.sup.m) are linearly independent over GF(2), that is, that b.sub.0 +b.sub.1 A+b.sub.2 A.sup.2 +. . . +b.sub.m-1 A.sup.m-1 vanishes only when the binary digits b.sub.0, b.sub.1, b.sub.2 . . . , b.sub.m-1 are all zeroes. The conventional approach is then to assign the unit vectors of length m with binary components to the elements 1, A, A.sup.2, . . . , A.sup.m-1.
As a specific example of the conventional approach, consider the finite field GF(2.sup.3) with the choice EQU P(X)=X.sup.3 +X+1 (2)
for the irreducible polynomial of degree 3. The next step is to define A as an element of GF(2.sup.3) such that EQU A.sup.3 +A+1=0 (3)
The following assignment of unit vectors is then made: ##EQU1## An arbitrary element B of GF(2.sup.3) is now represented by the binary vector [b.sub.2, b.sub.1, b.sub.0 ] with the meaning that EQU B=[b.sub.2, b.sub.1, b.sub.0 ]=b.sub.2 A.sup.2 +b.sub.1 A+b.sub.0 ( 5)
Let C=[c.sub.2, c.sub.1, c.sub.0 ] be a second element of GF(2.sup.3). It follows from equations (4) and (5) that EQU B+C=[b.sub.2 +c.sub.2, b.sub.1 +c.sub.1, b.sub.0 +c.sub.0 ]. (6)
Thus, in the conventional approach, addition in GF(2.sup.m) is easily performed by logic circuitry that merely forms the modulo-two sum of the two vectors representing the elements to be summed component-by-component. Multiplication is, however, considerably more complex to implement. Continuing the example, one sees from equation (3) that EQU A.sup.3 =A+1 EQU A.sup.4 =A.sup.2 +A (7)
where use has been made of the fact that -1=+1 in GF(2). From the equations (4), (5) and (7) it follows that EQU B.times.C=[d.sub.2, d.sub.1, d.sub.0 ] (8)
where EQU d.sub.0 =b.sub.0 c.sub.0 +b.sub.1 c.sub.2 +b.sub.2 c.sub.1 EQU d.sub.1 =b.sub.0 c.sub.1 +b.sub.1 c.sub.0 +b.sub.1 c.sub.2 +b.sub.2 c.sub.1 +b.sub.2 c.sub.2 EQU d.sub.2 =b.sub.0 c.sub.2 +b.sub.2 c.sub.0 +b.sub.1 c.sub.1 +b.sub.2 c.sub.2 ( 9)
Complex logic circuitry is required to implement equations (9). Upon taking C=B in equation (8), it follows from equation (9) that EQU B.sup.2 =[e.sub.2, e.sub.1, e.sub.0 ] (10)
where EQU e.sub.0 =b.sub.0 EQU e.sub.1 =b.sub.2 EQU e.sub.2 =b.sub.1 +b.sub.2 ( 11)
and where use has been made of the facts that b.sup.2 =b and b+b=0 in GF(2). Whereas the squaring rule of equations (11) is considerably simpler to implement than the multiplication rule of equations (9), it still has the disadvantage that some additions (in the example, only one) must be performed and that the form of the squaring rule varies among the components of the square.
By way of summary, one can say that the conventional approach to the design of logic circuitry to perform operations in GF(2.sup.m) leads to simple circuitry for addition, somewhat more complex circuitry for squaring, and very complex circuitry for multiplication.
One object of the present invention is to provide a new and improved multiplication method and apparatus for the finite field GF(2.sup.m). Another object is to provide this new and improved multiplication method and apparatus in combination with simple squaring means and addition means to obtain a new and improved method and apparatus for computation in GF(2.sup.m).